package week8;

/**
 *
 *
 * 684. 冗余连接
 * https://leetcode-cn.com/problems/redundant-connection/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
 * 内存消耗：38.5 MB, 在所有 Java 提交中击败了86.76% 的用户
 * 通过测试用例：39 / 39
 * 炫耀一下:
 *
 */
public class Week8RedundantConnection {

    public int find(int[] pointArray, int index) {
        if(pointArray[index] != index) {
            pointArray[index] = find(pointArray, pointArray[index]);
        }
        return pointArray[index];
    }

    public void union(int[] pointArray, int firstIndex, int secondIndex) {
        pointArray[find(pointArray, firstIndex)] = find(pointArray, secondIndex);
    }

    public int[] findRedundantConnection(int[][] edges) {
        int length = edges.length;
        int[] pointArray = new int[length + 1];
        for(int size = 1; size <= length; size++) {
            pointArray[size] = size;
        }
        for(int size = 0; size < length; size++) {
            int[] edge = edges[size];
            int node1 = edge[0];
            int node2 = edge[1];
            if(find(pointArray, node1) != find(pointArray, node2)) {
                union(pointArray, node1, node2);
            } else {
                return edge;
            }
        }

        return new int[0];
    }


}
